package Demo50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 计算右侧⼩于当前元素的个数（hard）
 * https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
 */

class Solution {
    int[] ret;
    int[] tmp1;
    int[] tmp2;


    public List<Integer> countSmaller(int[] nums) {
        int length = nums.length;
        // 构建返回数组和辅助数组
        List<Integer> list = new ArrayList<>();
        int[] index  = new int[length];
        tmp2 = new int[length];
        tmp1 = new int[length];
        ret = new int[length];
        for(int i = 0; i < length;i++) index[i] = i;
        margetSort( nums, index, 0, length - 1);
        System.out.println(ret);
        for(int n : ret) {
            list.add(n);
        }
        return list;
    }

    private void margetSort(int[] nums, int[] index, int begin, int end) {
        if(begin >= end) {
            return;
        }

        int mid = (end - begin) / 2 + begin;

        margetSort(nums, index, begin, mid);
        margetSort(nums, index,mid+1, end);

        int i = 0, left = begin, right = mid + 1;
        while(left <= mid && right <= end) {
            if(nums[left] <= nums[right]) {
               tmp1[i] = nums[right];
               tmp2[i++] = index[right++];
            }else {
                ret[index[left]] += end - right + 1;

                // 跟更新返回值
                tmp1[i] = nums[left];
                tmp2[i++] = index[left++];
            }
        }

        // 处理边界值
        while(left <= mid) {
            tmp1[i] = nums[left];
            tmp2[i++] = index[left++];
        }
        while(right <= end) {
            tmp1[i] = nums[right];
            tmp2[i++] = index[right++];
        }
        // 归并
        for(int j = begin; j <= end; j++) {
            nums[j] = tmp1[j - begin];
            index[j] = tmp2[j - begin];
        }
    }
}

class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> ret = solution.countSmaller(new int[] {0,2,1});
        System.out.println(ret);
    }
}